|
A partition of a polygon is a set of primitive units (e.g. squares), which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example: a partition with a smallest number of units or with units of smallest total side-length. Polygon partitioning is an important class of problems in computational geometry. There are many different polygon partition problems, depending on the type of polygon being partitioned and on the types of units allowed in the partition. The term polygon decomposition is often used as a general term that includes both covering and partitioning.〔 == Applications == Polygon decomposition is applied in several areas:〔 * Pattern recognition techniques extract information from an object in order to describe, identify or classify it. An established strategy for recognising a general polygonal object is to decompose it into simpler components, then identify the components and their interrelationships and use this information to determine the shape of the object. * In VLSI artwork data processing, layouts are represented as polygons, and one approach to preparation for electron-beam lithography is to decompose these polygon regions into fundamental figures. Polygon decomposition is also used in the process of dividing the routing region into channels. * In computational geometry, algorithms for problems on general polygons are often more complex than those for restricted types of polygons such as convex or star-shaped. The point inclusion problem is one example. A strategy for solving some of these types of problems on general polygons is to decompose the polygon into simple component parts, solve the problem on each component using a specialized algorithm, and then combine the partial solutions. * Other applications include data compression, database systems, image processing and computer graphics. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Polygon partition」の詳細全文を読む スポンサード リンク
|